package 简单算法;

import java.util.List;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-17
 * @Description: 翻转一个链表
 * 样例
 * 样例 1:
 * 输入: 1->2->3->null
 * 输出: 3->2->1->null
 * 样例 2:
 * 输入: 1->2->3->4->null
 * 输出: 4->3->2->1->null
 * 挑战
 * 在原地一次翻转完成
 **/
public class 翻转链表 {
    public static void main(String[] args) {
        翻转链表 s = new 翻转链表();

        ListNode head = new ListNode(1);
        ListNode two = new ListNode(2);
        ListNode three = new ListNode(3);
        head.next = two;
        two.next = three;
        ListNode node = s.reverse(head);
        s.dfs(node);
    }

    private void dfs(ListNode node) {
        if (node != null) {
            System.out.println(node.val);
            dfs(node.next);
        }
    }

    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head!=null){
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }

}


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}
